package _01_动态数组;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class _496_下一个更大元素I {

    public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        // 单调栈寻求最大值
        LinkedList<Integer> queue = new LinkedList<>();
        // 从后往前遍历
        for (int i = nums2.length - 1; i >= 0; i--) {
            while (!queue.isEmpty() && nums2[i] > queue.peek()) {
                queue.poll();
            }
            map.put(nums2[i], queue.isEmpty()? -1: queue.peek());
            queue.push(nums2[i]);
        }

        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = map.get(nums1[i]);
        }
        return nums1;
    }

    // Hash表顺序取得最大值
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        // 初始化末尾数据
        map.put(nums2[nums2.length - 1], -1);
        // 从后往前遍历
        for (int i = nums2.length - 2; i >= 0; i--) {
            // 假设下一个为当前位置的最大值
            int nextMax = nums2[i + 1];
            while (nextMax != -1 && nextMax < nums2[i]) {
                // 直到找到大于当前值的值
                nextMax = map.get(nextMax);
            }
            map.put(nums2[i], nextMax);
        }

        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = map.get(nums1[i]);
        }
        return nums1;
    }
}
